#include <bits/stdc++.h>

using namespace std;

class Interval
{
public:
    int start, end;
    Interval(int start, int end)
    {
        this->start = start;
        this->end = end;
    }
};

bool less_Interval(Interval i1, Interval i2)
{
    return i2.start < i1.start;
}

void printVector(vector<Interval> &intervals)
{
    for(int i = 0; i < intervals.size(); i++)
        printf("%d %d\t", intervals[i].start, intervals[i].end);
    printf("%d\n", intervals.size());
}
/**
* @param intervals: Sorted interval list.
* @param newInterval: new interval.
* @return: A new interval list.
*/
vector<Interval> insert(vector<Interval> &intervals, Interval newInterval)
{
    // write your code here
    //多种情况：无影响直接按照顺序插入；会和一个区间合并；会和两个区间合并；合并过程中插入区间可能包含了若干已有区间，删除这些区间；被已有区间包括，忽略
    int marge = -1;
    if(intervals.empty())
        intervals.push_back(newInterval);
    else if(newInterval.end < intervals[0].start)
        intervals.insert(intervals.begin(), newInterval);
    else if(newInterval.start > intervals[intervals.size() - 1].end)
        intervals.push_back(newInterval);
    else
    {
        vector<Interval>::iterator theIterator = intervals.begin();;
        for(int i = 0; i < intervals.size(); i++, theIterator++)
        {
            if(newInterval.start <= intervals[i].start && newInterval.end >= intervals[i].end)
            {
                intervals.erase(theIterator);
                if(marge < 0)
                {
                    intervals.insert(theIterator, newInterval);
                    marge = i;
                }
                else
                {
                    i--;
                    theIterator--;
                }
            }
            else if(newInterval.start >= intervals[i].start && newInterval.end <= intervals[i].end)
                break;
            else if(newInterval.start > intervals[i].end && i + 1 < intervals.size() && newInterval.end < intervals[i + 1].start)
            {
                intervals.insert(theIterator+1, newInterval);
                break;
            }
            else if(newInterval.start >= intervals[i].start && newInterval.start <= intervals[i].end)
            {
                intervals[i].end = newInterval.end;
                marge = i;
            }
            else if(newInterval.end <= intervals[i].end && newInterval.end >= intervals[i].start)
            {
                if(marge >= 0)
                {
                    intervals[marge].end = intervals[i].end;
                    intervals.erase(theIterator);
                    break;
                }
                else
                    intervals[i].start = newInterval.start;
                marge = i;
            }
        }
//    if(marge < 0)
//        intervals.push_back(newInterval);
//    sort(intervals.begin(), intervals.end(), less_Interval);
    }
    return intervals;
}

int main()
{
    Interval i1(2, 5), i2(1, 2), i3(5, 9), i4(3, 4), i5(1, 2), i6(5, 9);
    vector<Interval> v1, v2, v3, v4;
    insert(v1, i2);
    printVector(v1);
    insert(v1, i3);
    printVector(v1);
    insert(v1, i1);
    printVector(v1);
    insert(v1, Interval(10, 12));
    printVector(v1);

    insert(v2, i6);
    printVector(v2);
    insert(v2, i5);
    printVector(v2);
    insert(v2, i4);
    printVector(v2);

    insert(v3, Interval(1, 5));
    printVector(v3);
    insert(v3, Interval(2, 3));
    printVector(v3);
    insert(v3, Interval(1, 9));
    printVector(v3);
    insert(v3, Interval(11, 12));
    printVector(v3);
    insert(v3, Interval(0, 19));
    printVector(v3);

    insert(v4, Interval(1, 5));
    printVector(v4);
    insert(v4, Interval(7, 8));
    printVector(v4);
    insert(v4, Interval(10, 13));
    printVector(v4);
    insert(v4, Interval(6, 7));
    printVector(v4);
    return 0;
}

/**


给出一个无重叠的按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
您在真实的面试中是否遇到过这个题？
样例

插入区间(2, 5) 到 [(1,2), (5,9)]，我们得到 [(1,9)]。

插入区间(3, 4) 到 [(1,2), (5,9)]，我们得到 [(1,2), (3,4), (5,9)]。
*/
